package sort.merge.二路归并;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * User:Mr.Du
 * Date:2021/6/1
 * Time:22:13
 */

import java.util.Arrays;
import java.util.Random;
//归并排序
public class 二路归并 {
    public static void main(String[] args) {
        Random r = new Random();
        int[] arr = new int[10];
        for(int i = 0;i<arr.length;i++){
            arr[i] = r.nextInt(50);
        }
        System.out.println(arr);
        mergeSort(arr,0,10-1);
        //System.out.println(arr);
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();

    }
    public static void mergeSort(int[] arr,int begin,int end){
        if(begin >= end){
            return;
        }
        int mid = (begin+end)/2;
        mergeSort(arr,begin,mid);
        mergeSort(arr,mid+1,end);
        Merge(arr,begin,mid,end);
    }
    //将左右两边分成两个数组进行归并
    public static void Merge(int[] arr,int begin,int mid,int end){
        //int mid = (begin+end)/2;
        //定义一个临时数组
        int[] temp = new int[end-begin+1];
        //数组起点到终点,给临时数组赋值。
        for(int i=begin;i<=end;i++){
            temp[i-begin] = arr[i];
        }
        //i,j分别为左右两边数组元素的起始下标
        int i = begin;
        int j = mid+1;
        for(int k=begin;k<=end;k++){
            if(i>mid){
                //检查左半边下标是否越界,若越界就是右边
                arr[k] = temp[j-begin];
                j++;
            } else if(j > end) {
                //检查右边下标是否越界
                arr[k] = temp[i-begin];
                i++;
            } else if(temp[i-begin] <= temp[j-begin]) {
                //判断左右两边元素的大小
                arr[k] = temp[i-begin];
                i++;
            } else {
                arr[k] = temp[j-begin];
                j++;
            }
        }
    }
}


